package com.example.demofdfs.example.link;

import java.io.Serializable;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;


@SuppressWarnings("serial")
public class DoubleLinked<E> implements Links<E>, Serializable, Cloneable {

	/**
	 * 元素数量
	 */
	private int size;
	/**
	 * 记录第一个节点的指针.
	 */
	private Node<E> first;
	/**
	 * 记录了最后一个节点的指针
	 */
	private Node<E> last;
	/**
	 * 统计这个数据结构发生变化的次数, add / remove 操作会导致结构上的改变
	 */
	protected int modCount;
	
	/**
	 * 记录数据的节点
	 *
	 * @param <E>
	 */
	private static class Node<E> {
		private Node<E> prev;
		private E item;
		private Node<E> next;
		public Node(Node<E> prev, E item, Node<E> next) {
			super();
			this.prev = prev;
			this.item = item;
			this.next = next;
		}
		
	}
	
	/**
	 * 迭代器实现,
	 *
	 */
	private class LinkItr implements Iterator<E> {

		/**
		 * 最后返回的节点指针, 初始为null
		 */
		private Node<E> lastReturn;
		/**
		 * 光标, 下一个节点索引
		 */
		private int cursor;
		/**
		 * 下一个返回的节点指针, 初始为 first 节点
		 */
		private Node<E> node;
		/**
		 * 判断是否被并发修改过的计数器
		 */
		private int expectedModCount = modCount;
		
		public LinkItr() {
			this.node = first;
		}
		
		@Override
		public boolean hasNext() {
			return cursor < size;
		}

		@Override
		public E next() {
			checkConcurrentModification();
			if(! hasNext())
				throw new NoSuchElementException();
			if (node == null) {
				throw new NoSuchElementException();
			}
			lastReturn = node;
			node = node.next;
			cursor++;
			return lastReturn.item;
		}
		
		@Override
		public void remove() {
			if (lastReturn == null) {
				throw new NoSuchElementException();
			}
			unlink(lastReturn);
			this.expectedModCount = modCount;
			lastReturn = null;
			cursor--;
		}

		void checkConcurrentModification() {
			if (expectedModCount != modCount) {
				throw new ConcurrentModificationException();
			}
		}
	}

	@Override
	public boolean add(E e) {
		Node<E> l = last;
		Node<E> newNode = new Node<E>(l, e, null);
		last = newNode;
		if (l == null) {
			first  = newNode;
		} else {
			l.next = newNode;
		}
		size++;
		modCount++;
		return true;
	}

	@Override
	public E get(int index) {
		checkIndex(index);
		return node(index).item;
	}
	
	/**
	 * 检查索引是否越界
	 * @param index
	 */
	private void checkIndex(int index) {
		if (index >= size || index < 0)
			throw new IndexOutOfBoundsException("index out : " + index);
	}

	Node<E> node(int index) {
		Node<E> f = first;
		for(int i = 0; i < index; i++) {
			f = f.next;
		}
		return f;
	}

	@Override
	public E remove(int index) {
		checkIndex(index);
		return unlink(node(index));
	}
	
	/**
	 * 从链表中断开指定的节点;
	 * @param node
	 * @return
	 */
	E unlink(Node<E> node) {
//		if (node == null) {
//			return null;
//		}
		E e = node.item;
		Node<E> prev = node.prev;
		Node<E> next = node.next;
		
		// 交换头节指针
		if (prev == null) {
			first = next;
		} else {
			prev.next = next;
			node.prev = null;
		}
		
		// 交换尾节点指针
		if (next == null) {
			last = prev;
		} else {
			next.prev = prev;
			node.next = null;
		}
		
		node.item = null;
		size--;
		modCount++;
		return e;
	}

	@Override
	public E set(int index, E e) {
		checkIndex(index);
		Node<E> n = node(index);
		E oldValue = n.item;
		n.item = e;
		return oldValue;
	}
	
	@Override
	public Iterator<E> iterator() {
		return new LinkItr();
	}

	@Override
	public int size() {
		return size;
	}
	
	@Override
	public Object clone() throws CloneNotSupportedException {
		return super.clone();
	}

	@Override
	public String toString() {
		Iterator<E> it = iterator();
		while(!it.hasNext()) {
			return "[]";
		}
		StringBuilder sb = new StringBuilder();
		sb.append('[');
		while(true) {
			sb.append(it.next());
			if (! it.hasNext())
				return sb.append(']').toString();
			sb.append(",").append(' ');
		}
	}
	

}
